package binaryTree;

import java.util.HashMap;
import java.util.Stack;

public class Class662 {

    public int widthOfBinaryTree(TreeNode root) {
        if (root==null){
            return 0;
        }
        Stack<TreeNode> st = new Stack<TreeNode>();
        st.push(root);
        int maxWidth=Integer.MIN_VALUE;
        int depth=0;
        HashMap<Integer, Integer> map = new HashMap<>();
        while (!st.isEmpty()){
            depth++;
            int size = st.size();
            maxWidth=maxWidth< size?size:maxWidth;
            map.put(maxWidth,depth);
            for (int i = 0; i < size; i++) {
                TreeNode node = st.pop();
                if (node.left!=null){
                    st.push(node.left);
                }
                if (node.right!=null){
                    st.push(node.right);
                }

            }
        }
        int wide_depth = map.get(maxWidth);
        int max= (int) Math.pow(2,wide_depth);
        maxWidth=maxWidth<max?max:maxWidth;
        return  maxWidth;

    }
}
